package com.le.basic.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树
 * 搜索二叉树: BST --> 左子树小于根,右子树大于根
 * 完全二叉树: 结点按层放置,所有结点从左致右依次放置
 */
public class Code_07_IsBSTAndCBT {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 判断是否是二叉搜索树
     * @param head
     * @return
     */
    public static boolean isBST(Node head){
        if (head == null){
            return false;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()){
            head = queue.poll();
            Node leftNode = head.left;
            Node rightNode = head.right;
            // 左右子树都不为空
            if (leftNode != null && rightNode != null){
                if (leftNode.value < head.value){
                    queue.offer(leftNode);
                }else {
                    return false;
                }
                if (rightNode.value > head.value){
                    queue.offer(rightNode);
                }else {
                    return false;
                }
            }else if (leftNode != null && rightNode == null){ //左子树不为空,右子树为空
                if (leftNode.value < head.value){
                    queue.offer(leftNode);
                }else {
                    return false;
                }
            }else if (leftNode == null && rightNode != null){
                if (rightNode.value > head.value){
                    queue.offer(rightNode);
                }else {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 判断是否是完全二叉树
     * @param head
     * @return
     */
    public static boolean isCBT(Node head){
        if (head == null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        boolean flag = false; // 判断是否开启叶子结点判断
        queue.offer(head);
        while (!queue.isEmpty()){
            head = queue.poll();
            Node leftNode = head.left;
            Node rightNode = head.right;
            if (!flag){
                // 不是叶子结点
                if (leftNode != null && rightNode != null){
                    queue.offer(leftNode);
                    queue.offer(rightNode);
                }else if (leftNode != null && rightNode == null){
                    queue.offer(leftNode);
                    flag = true;
                }else if (rightNode != null && leftNode == null){
                    return false;
                }
            }else {
                if ((leftNode != null && rightNode != null) || (leftNode == null || rightNode == null)){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
//        head.right.left = new Node(7);
        head.right.right = new Node(9);
//        boolean flag = isBST(head);
//        System.out.println(flag);
        boolean cbt = isCBT(head);
        System.out.println(cbt);
    }
}
